It is common in the study of networks to investigate meso-scale features totry to gain an understanding of network structure and function. For example,numerous algorithms have been developed to try to identify "communities," whichare typically construed as sets of nodes with denser connections internallythan with the remainder of a network. In this paper, we adopt a complementaryperspective that "communities" are associated with bottlenecks oflocally-biased dynamical processes that begin at seed sets of nodes, and weemploy several different community-identification procedures (usingdiffusion-based and geodesic-based dynamics) to investigate community qualityas a function of community size. Using several empirical and syntheticnetworks, we identify several distinct scenarios for ``size-resolved communitystructure'' that can arise in real (and realistic) networks. Depending on whichscenario holds, one may or may not be able to successfully identify ``good''communities in a given network, the manner in which different small communitiesfit together to form meso-scale network structures can be very different, andprocesses such as viral propagation and information diffusion can exhibit verydifferent dynamics.In addition, our results suggest that, for many largerealistic networks, the output of locally-biased methods that focus oncommunities that are centered around a given seed node might have betterconceptual grounding and greater practical utility than the output of globalcommunity-detection methods. They also illustrate subtler structural propertiesthat are important to consider in the development of better benchmark networksto test methods for community detection. [Note: Because of space limitations in the arXiv's abstract field, this is anabridged version of the paper's abstract.]
展开▼
